package 分类.一维动规;

import java.util.ArrayList;
import java.util.Arrays;

public class 打家劫舍2 {
    public int rob(int[] nums) {
        int n=nums.length;
        if(n==0) return 0;
        if(n==1) return nums[0];
        int[] memo1=new int[n];
        int[] memo2=new int[n];
        Arrays.fill(memo1,-1);
        Arrays.fill(memo2,-1);
        int res1=dp(nums,0,n-2,memo1);
        int res2=dp(nums,1,n-1,memo2);
        return Math.max(res1,res2);
    }

    int dp(int[] nums,int start,int end,int[] memo){
        if(start>end) return 0;
        if(memo[start]!=-1) return memo[start];
        memo[start]=Math.max(dp(nums,start+2,end,memo)+nums[start],dp(nums,start+1,end,memo));
        return memo[start];
    }
}
